import java.util.LinkedList;
import java.util.Queue;

public class Solution1293 {
    public int shortestPath(int[][] grid, int k) {
        if (grid.length==grid[0].length && grid.length==1){
            return 0;
        }
        int[][][] visit=new int[grid.length][grid[0].length][k+1];
        for (int i=0;i<grid.length;i++){
            for (int j=0;j<grid[0].length;j++){
                for (int t=0;t<=k;t++){
                    visit[i][j][t]=Integer.MAX_VALUE;
                }
            }
        }
        visit[0][0][0]=0;
        Queue<int[]> queue=new LinkedList<>();
        queue.offer(new int[]{0,0,0});
        int[] dx=new int[]{0,1,0,-1};
        int[] dy=new int[]{1,0,-1,0};
        while (!queue.isEmpty()){
            int[] t=queue.poll();
            for (int i = 0; i < 4; i++) {
                int x=t[0]+dx[i];
                int y=t[1]+dy[i];
                if (x>=0 && x<grid.length && y>=0 && y<grid[0].length){
                    if (grid[x][y]==1 && t[2]==k){
                        continue;
                    }
                    if (visit[x][y][t[2]+grid[x][y]]==Integer.MAX_VALUE){
                        queue.offer(new int[]{x,y,t[2]+grid[x][y]});
                        visit[x][y][t[2]+grid[x][y]]=visit[t[0]][t[1]][t[2]]+1;
                        if (x==grid.length-1 && y==grid[0].length-1){
                            return visit[x][y][t[2]+grid[x][y]];
                        }
                    }
                }
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        System.out.println(new Solution1293().shortestPath(new int[][]{{0,0,0},{1,1,0},{0,0,0},{0,1,1},{0,0,0}},1));
    }
}
